原题大意:给定给一个有两个核的CPU,一共要执行个模块,每个模块在A核上运行的时间是.在B核上的时间是.给出对之间需要进行数据交换的模块组合.如果两者在同一核上运行则不需要额外代价,否则需要额外的的时间.
数据范围:
思路
整个问题可以这么考虑:把所有的模块都分成两堆,分别在A核上执行或者在B核上执行,那么实际上就是根据代价求一个最小割,先把割是什么确定下来.
源点是,汇点是.把在A核上执行的集合记作S,在B核上执行的集合记作T.那么割里对应过来就是S包含s,T包含t.这样两个集合就划分完毕了.最后总的代价就是对于最小割来说,最小化的是容量,因此把割的容量作为代价再建图就可以解决了.考虑具体怎么建图:
对于表达式里的.就是说明属于集合的某个点要在A核上运行,产生了的代价.对于割来说,你选了A就不能选B,这是一个断开的关系,因此是从点连向汇点t,容量就是代价.最小割问题求解的是:让s到t没有一个路径,最少删边的容量之和.就是这个边应该是两个集合之间的连边,他不是集合内部的.对于同理让源点连向即可.
对于剩下两个两个点的关系,直接连边即可.当这这两个集合之间的所有边都被删掉之后,自然就不联通了.而最小割-最大流定理在这里可以可以继续转化问题,把求解最小割的问题变成一个求解最大流的问题.因此只要在建立的新图上求最大流就是答案了.
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7,M = 1e6+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N];
ll incf[N],maxflow;
queue<int> q;
void add(int u,int v,int w)
{
edge[++idx] = v;
cap[idx] = w;
succ[idx] = ver[u];
ver[u] = idx;
edge[++idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx;
}
bool bfs()
{
memset(d,0,sizeof d);
while(q.size()) q.pop();
q.push(s);d[s] = 1;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = ver[u];i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
q.push(v);
d[v] = d[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int flow)
{
if(u == t) return flow;
int rest = flow,k,i;
for(int i = ver[u];i && rest;i = succ[i])
{
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
k = dinic(v,min(rest,cap[i]));
if(!k) d[v] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
int main()
{
scanf("%d%d",&n,&m);
s = 0;t = n + 1;
for(int i = 1;i <= n;++i)
{
int a,b;scanf("%d%d",&a,&b);
add(i,t,a);
add(s,i,b);
}
for(int i = 0;i < m;++i)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
int flow = 0;
while(bfs())
while(flow = dinic(s,INF))
maxflow += flow;
printf("%lld",maxflow);
return 0;
}